package q406_reconstructQueue;

import java.util.Arrays;
import java.util.LinkedList;

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 先将身高从大到小排列 如果身高相同 则k小的排在前面
        Arrays.sort(people, (p1, p2) -> {
            if (p1[0] == p2[0]) return p1[1] - p2[1];
            return p2[0] - p1[0];
        });

        LinkedList<int[]> que = new LinkedList<>();

        /*
        对于队列的add方法：
        参数1为index
        参数2为插入队列的元素
        排序完的people：
        [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]
        插⼊的过程：
        插⼊[7,0]：[[7,0]]
        插⼊[7,1]：[[7,0],[7,1]]
        插⼊[6,1]：[[7,0],[6,1],[7,1]]
        插⼊[5,0]：[[5,0],[7,0],[6,1],[7,1]]
        插⼊[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
        插⼊[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

        例如 第一步插入的index为0 也就是插入到0的位置
        第二步为1 则插入到1的位置
        第三步为1 仍然插入为1位置
        第四步是0 插入到0的位置
        第五步是2 所以插入到队列中2的位置（0 1 2）
        。。。
        对于p[1]这个参数代表的意义实际上就是前面有几个高于他的人
         */
        for (int[] p : people) {
            que.add(p[1], p);
        }

        return que.toArray(new int[people.length][]);

    }
}
